{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Longest Univalue Path"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #tree #depth-first-search #binary-tree"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #树 #深度优先搜索 #二叉树"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: longestUnivaluePath"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #最长同值路径"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给定一个二叉树的<meta charset=\"UTF-8\" />&nbsp;<code>root</code>&nbsp;，返回&nbsp;<em>最长的路径的长度</em> ，这个路径中的&nbsp;<em>每个节点具有相同值</em>&nbsp;。 这条路径可以经过也可以不经过根节点。</p>\n",
    "\n",
    "<p><strong>两个节点之间的路径长度</strong>&nbsp;由它们之间的边数表示。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1:</strong></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode.com/uploads/2020/10/13/ex1.jpg\" /></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>root = [5,4,5,1,1,5]\n",
    "<strong>输出：</strong>2\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2:</strong></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode.com/uploads/2020/10/13/ex2.jpg\" /></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>root = [1,4,5,4,4,5]\n",
    "<strong>输出：</strong>2\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示:</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li>树的节点数的范围是<meta charset=\"UTF-8\" />&nbsp;<code>[0, 10<sup>4</sup>]</code>&nbsp;</li>\n",
    "\t<li><code>-1000 &lt;= Node.val &lt;= 1000</code></li>\n",
    "\t<li>树的深度将不超过 <code>1000</code>&nbsp;</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [longest-univalue-path](https://leetcode.cn/problems/longest-univalue-path/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [longest-univalue-path](https://leetcode.cn/problems/longest-univalue-path/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[5,4,5,1,1,null,5]', '[1,4,5,4,4,null,5]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def longestUnivaluePath(self, root: TreeNode) -> int:\n",
    "        \n",
    "        self.ans = 0\n",
    "        def walkPath(node):\n",
    "            if not node:\n",
    "                return 0\n",
    "            \n",
    "            leftLen = walkPath(node.left)\n",
    "            rightLen = walkPath(node.right)\n",
    "            \n",
    "            leftPath = rightPath = 0\n",
    "            if node.left and node.left.val == node.val:\n",
    "                leftPath = leftLen + 1\n",
    "                \n",
    "            if node.right and node.right.val == node.val:\n",
    "                rightPath = rightLen + 1\n",
    "            \n",
    "            self.ans = max(self.ans, leftPath+rightPath)\n",
    "            return max(leftPath, rightPath)\n",
    "        \n",
    "        walkPath(root)\n",
    "        return self.ans\n",
    "            \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution(object):\n",
    "    def __init__(self):\n",
    "        self.max_path = 0\n",
    "    def longestUnivaluePath(self, root):\n",
    "        \"\"\"\n",
    "        :type root: TreeNode\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        if not root:\n",
    "            return 0\n",
    "        res = [root]\n",
    "        while res:\n",
    "            r = res.pop()\n",
    "            left = self.find_path(r.left, r.val)\n",
    "            right = self.find_path(r.right, r.val)\n",
    "            if self.max_path < left + right:\n",
    "                self.max_path = left + right\n",
    "            if r.right:\n",
    "                res.append(r.right)\n",
    "            if r.left:\n",
    "                res.append(r.left)\n",
    "        return self.max_path\n",
    "\n",
    "    def find_path(self, root, value):\n",
    "        if not root:\n",
    "            return 0\n",
    "        if root.val != value:\n",
    "            return 0\n",
    "        else:\n",
    "            return max(self.find_path(root.left, value), self.find_path(root.right, value)) + 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def longestUnivaluePath(self, root):\n",
    "        \"\"\"\n",
    "        :type root: TreeNode\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        \n",
    "        \"\"\"\n",
    "            5(a)\n",
    "            /\n",
    "           5(b)\n",
    "         /    \\\n",
    "        5(c)   5(d)\n",
    "        \n",
    "        经过某一节点的最长的path，可能有三种情况\n",
    "        a-b-c\n",
    "        a-b-d\n",
    "        c-b-d\n",
    "        需要计算三种情况的最大值，\n",
    "        记录 a-b 的长度\n",
    "        记录 b-c 的长度\n",
    "        记录 b-d 的长度\n",
    "        \n",
    "        \"\"\"\n",
    "        def path(root,val_dict):\n",
    "            if root.val not in val_dict:\n",
    "                val_dict.update({root.val:0})\n",
    "                \n",
    "            if root.left==None and root.right==None:\n",
    "                return 0\n",
    "            # 左侧\n",
    "            left_val = 0\n",
    "            if root.left!=None:\n",
    "                if root.left.val == root.val:\n",
    "                    left_val = path(root.left,val_dict)+1\n",
    "                else:\n",
    "                    path(root.left,val_dict)\n",
    "                    \n",
    "            # 右侧     \n",
    "            right_val = 0\n",
    "            if root.right!=None:\n",
    "                if root.right.val == root.val:\n",
    "                    right_val = path(root.right,val_dict)+1\n",
    "                else:\n",
    "                    path(root.right,val_dict)\n",
    "            \n",
    "            # 更新dict\n",
    "            # 处理了多种情况，\n",
    "            # 1) right_val==0,left_val!=0\n",
    "            # 2) right_val!=0,left_val==0\n",
    "            # 3) right_val!=0,left_val!=0   c-b-d形式\n",
    "            if root.val in val_dict  and val_dict[root.val]< right_val+left_val:\n",
    "                val_dict[root.val] = right_val+left_val\n",
    "            \n",
    "            # 5(a) 需要这个数字\n",
    "            return max(left_val,right_val)\n",
    "        \n",
    "        val_dict = {}\n",
    "        if root!=None:\n",
    "            path(root,val_dict)\n",
    "            return max(val_dict.values())\n",
    "        return 0\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def longestUnivaluePath(self, root):\n",
    "        \"\"\"\n",
    "        :type root: TreeNode\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        \n",
    "        if root == None:\n",
    "            \n",
    "            return 0\n",
    "        \n",
    "        if root.left == None and root.right == None:\n",
    "            \n",
    "            return 0\n",
    "        \n",
    "        res = self.luipath(root,root.val)\n",
    "        \n",
    "        # print(self.temp)\n",
    "        \n",
    "        if res-1 > self.res:\n",
    "            \n",
    "            self.res = res-1\n",
    "        \n",
    "        self.longestUnivaluePath(root.left)\n",
    "        \n",
    "        self.longestUnivaluePath(root.right)\n",
    "        \n",
    "        return max(self.res,self.temp) \n",
    "    \n",
    "    \n",
    "    def luipath(self,root,k):\n",
    "        \n",
    "        if root == None:\n",
    "            \n",
    "            return 0\n",
    "        \n",
    "        if root.val == k:\n",
    "                \n",
    "            node = 1\n",
    "\n",
    "            left_val = self.luipath(root.left,k)\n",
    "            \n",
    "            right_val = self.luipath(root.right,k)\n",
    "            \n",
    "        else:\n",
    "            return 0\n",
    "        \n",
    "        if root.left != None and root.right != None and root.val == root.left.val and root.val == root.right.val:\n",
    "            \n",
    "            if left_val + right_val > self.temp:\n",
    "                \n",
    "                self.temp = left_val + right_val\n",
    "                \n",
    "            return node + max(left_val,right_val)\n",
    "        \n",
    "        else:\n",
    "            \n",
    "            return node + max(left_val,right_val)\n",
    "            \n",
    "            \n",
    "            \n",
    "    def __init__(self):\n",
    "        \n",
    "        \n",
    "        self.res = 0\n",
    "        \n",
    "        self.temp = 0\n",
    "        \n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def longestUnivaluePath(self, root):\n",
    "        \"\"\"\n",
    "        :type root: TreeNode\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        self.ans = 0\n",
    "        def treelengh(root):\n",
    "            if root == None:\n",
    "                return 0\n",
    "            left_lengh = treelengh(root.left)\n",
    "            right_lengh = treelengh(root.right)\n",
    "            left = 0\n",
    "            right = 0\n",
    "            if root.left and root.left.val == root.val:\n",
    "                left = left_lengh + 1\n",
    "            if root.right and root.right.val == root.val:\n",
    "                right = right_lengh + 1\n",
    "            self.ans = max(self.ans,left + right)\n",
    "            return max(left,right)\n",
    "        treelengh(root)\n",
    "        return self.ans\n",
    "                \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def longestUnivaluePath(self, root):\n",
    "        \"\"\"\n",
    "        :type root: TreeNode\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        if not root: return 0\n",
    "        self.res = 0\n",
    "        self.dfs(root)\n",
    "        return self.res\n",
    "\n",
    "    def dfs(self, node):\n",
    "        if not node: return 0\n",
    "        cur_len = 0\n",
    "        l_len, r_len = self.dfs(node.left), self.dfs(node.right)\n",
    "        l_len = l_len+1 if node.left and node.left.val==node.val else 0\n",
    "        r_len = r_len+1 if node.right and node.right.val==node.val else 0\n",
    "        self.res = max(self.res, l_len+r_len)\n",
    "        return max(l_len, r_len)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def longestUnivaluePath(self, root):\n",
    "        \"\"\"\n",
    "        :type root: TreeNode\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        if not root:\n",
    "            return 0\n",
    "        self.res = 0\n",
    "        self.help(root)\n",
    "        return self.res\n",
    "    \n",
    "    def help(self,node):\n",
    "        if not node:\n",
    "            return 0\n",
    "#         左节点的长度\n",
    "        l = self.help(node.left)\n",
    "        r = self.help(node.right)\n",
    "        lc=rc = 0\n",
    "        if node.left and node.left.val == node.val:\n",
    "            lc = l+1\n",
    "        else:\n",
    "            lc=0\n",
    "        if node.right and node.right.val == node.val:\n",
    "            rc = r+1\n",
    "        else:\n",
    "            rc=0\n",
    "        self.res = max(self.res,lc+rc)\n",
    "        return max(lc,rc)\n",
    "            \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def longestUnivaluePath(self, root: 'TreeNode') -> 'int':\n",
    "        self.ans = 0\n",
    "        \n",
    "        def tree_path(node: 'TreeNode') -> 'int':\n",
    "            if not node:\n",
    "                return 0\n",
    "            \n",
    "            left_length = tree_path(node.left)\n",
    "            right_length = tree_path(node.right)\n",
    "            \n",
    "            left_arrow = right_arrow = 0\n",
    "            if node.left and node.left.val == node.val:\n",
    "                left_arrow = left_length + 1\n",
    "            if node.right and node.right.val == node.val:\n",
    "                right_arrow = right_length + 1\n",
    "                \n",
    "            self.ans = max(self.ans, left_arrow + right_arrow)\n",
    "            \n",
    "            return max(left_arrow, right_arrow)\n",
    "        \n",
    "        tree_path(root)\n",
    "        \n",
    "        return self.ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    path = 0\n",
    "    def longestUnivaluePath(self, root):\n",
    "        \"\"\"\n",
    "        :type root: TreeNode\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        self.dfs(root)\n",
    "        return self.path\n",
    "        \n",
    "    def dfs(self, root):\n",
    "        if not root:\n",
    "            return 0\n",
    "        left = self.dfs(root.left)\n",
    "        right = self.dfs(root.right)\n",
    "        leftpath = left + 1 if root.left != None and root.left.val == root.val else 0\n",
    "        rightpath = right + 1 if root.right != None and root.right.val == root.val else 0\n",
    "        self.path = max(self.path, leftpath + rightpath)\n",
    "        return max(leftpath, rightpath)\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def longestUnivaluePath(self, root):\n",
    "        \"\"\"\n",
    "        :type root: TreeNode\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        ans = 0\n",
    "        def dfs(n):\n",
    "            nonlocal ans\n",
    "            l = r = 0\n",
    "            if n.left:\n",
    "                tmp = dfs(n.left)\n",
    "                if n.left.val == n.val:\n",
    "                    l = tmp + 1\n",
    "            if n.right:\n",
    "                tmp = dfs(n.right)\n",
    "                if n.right.val == n.val:\n",
    "                    r = tmp + 1\n",
    "            ans = max(ans, l + r)\n",
    "            return max(l, r)\n",
    "\n",
    "        if root:\n",
    "            dfs(root)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def longestPath(self, root: 'TreeNode') -> 'list':\n",
    "        if not root:\n",
    "            return [0, 0, 0]\n",
    "        straight_len = max_curve_len = max_other_len = 0\n",
    "        left_s_len = left_mc_len = 0\n",
    "        right_s_len = right_mc_len = 0\n",
    "        left_is_same = right_is_same = False\n",
    "        if root.left:\n",
    "            if root.left.val == root.val:\n",
    "                left_is_same = True\n",
    "                left_s_len, left_mc_len, tmp_len = self.longestPath(root.left)\n",
    "                straight_len = left_s_len + 1\n",
    "                if tmp_len > max_other_len:\n",
    "                    max_other_len = tmp_len\n",
    "            else:\n",
    "                max_other_len = self.longestUnivaluePath(root.left)\n",
    "        if root.right:\n",
    "            if root.right.val == root.val:\n",
    "                right_is_same = True\n",
    "                right_s_len, right_mc_len, tmp_len = self.longestPath(root.right)\n",
    "                if right_s_len >= left_s_len:\n",
    "                    straight_len = right_s_len + 1\n",
    "                if tmp_len > max_other_len:\n",
    "                    max_other_len = tmp_len\n",
    "            else:\n",
    "                tmp_len = self.longestUnivaluePath(root.right)\n",
    "                if tmp_len > max_other_len:\n",
    "                    max_other_len = tmp_len\n",
    "        if left_is_same and right_is_same:\n",
    "            tmp_len = left_s_len + right_s_len + 2\n",
    "        else:\n",
    "            tmp_len = 0\n",
    "        max_curve_len = max(left_mc_len, right_mc_len, tmp_len)\n",
    "        return [straight_len, max_curve_len, max_other_len]\n",
    "\n",
    "    def longestUnivaluePath(self, root: 'TreeNode') -> 'int':\n",
    "        if not root:\n",
    "            return 0\n",
    "        straight_len, max_curve_len, max_other_len = self.longestPath(root)\n",
    "        return max(straight_len, max_curve_len, max_other_len)\n",
    "            \n",
    "            \n",
    "            \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    diameter = 0\n",
    "\n",
    "    def dfs(self, root, roots):\n",
    "        if root is None:\n",
    "            return\n",
    "        if root.left:\n",
    "            self.dfs(root.left, roots)\n",
    "            if root.left.val != root.val:\n",
    "                roots.append(root.left)\n",
    "                root.left = None\n",
    "        if root.right:\n",
    "            self.dfs(root.right, roots)\n",
    "            if root.right.val != root.val:\n",
    "                roots.append(root.right)\n",
    "                root.right = None\n",
    "\n",
    "\n",
    "    def cnt(self, root):\n",
    "        if root is None:\n",
    "            return 0\n",
    "        l = self.cnt(root.left)\n",
    "        r = self.cnt(root.right)\n",
    "        self.diameter = max(self.diameter, l + r)\n",
    "        return max(l, r) + 1\n",
    "\n",
    "\n",
    "    def longestUnivaluePath(self, root: TreeNode) -> int:\n",
    "        roots = [root]\n",
    "        self.dfs(root, roots)\n",
    "        ans = 0\n",
    "        for r in roots:\n",
    "            self.diameter = 0\n",
    "            self.cnt(r)\n",
    "            ans = max(ans, self.diameter)\n",
    "        return ans\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.length = 0\n",
    "\n",
    "    def longestUnivaluePath(self, root: TreeNode) -> int:\n",
    "\n",
    "        def getMaxL(root, val):\n",
    "            if not root:\n",
    "                return 0\n",
    "            l = getMaxL(root.left, root.val)\n",
    "            r = getMaxL(root.right, root.val)\n",
    "\n",
    "            self.length = max(self.length, r+l)\n",
    "\n",
    "            return max(l, r) + 1 if root.val == val else 0\n",
    "        \n",
    "        if root:\n",
    "            getMaxL(root, root.val)\n",
    "        return self.length\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def longestUnivaluePath(self, root: TreeNode) -> int:\n",
    "        if not root: return 0\n",
    "        \n",
    "        ans = 1  # 路径节点数\n",
    "        def solve(root):\n",
    "            \"\"\"\n",
    "            返回以root为端点最长的路径的节点数\n",
    "            \"\"\"\n",
    "            nonlocal ans\n",
    "            \n",
    "            if not root.left and not root.right: \n",
    "                return 1\n",
    "            \n",
    "            left_len = right_len = 0\n",
    "            \n",
    "            if root.left:\n",
    "                left_len = solve(root.left)\n",
    "                if root.left.val == root.val:\n",
    "                    ans = max(ans, 1 + left_len)\n",
    "            \n",
    "            if root.right:\n",
    "                right_len = solve(root.right)\n",
    "                if root.right.val == root.val:\n",
    "                    ans = max(ans, 1 + right_len)                    \n",
    "            \n",
    "            if root.left and root.right:\n",
    "                if root.left.val == root.right.val == root.val:\n",
    "                    ans = max(ans, 1 + left_len + right_len)\n",
    "            \n",
    "            return 1 + max(left_len if root.left and root.left.val == root.val else 0, \n",
    "                           right_len if root.right and root.right.val == root.val else 0)\n",
    "        \n",
    "        solve(root)\n",
    "        return ans - 1\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    maxLen = 0\n",
    "    def longestUnivaluePath(self, root: TreeNode) -> int:\n",
    "        if  not root: return 0\n",
    "        self.cal(root)\n",
    "        return self.maxLen\n",
    "\n",
    "    def cal(self, root: TreeNode):\n",
    "        if not root: return 0\n",
    "        left = self.cal(root.left)\n",
    "        right = self.cal(root.right)\n",
    "        if root.left and root.val == root.left.val:\n",
    "            left += 1\n",
    "        else:\n",
    "            left = 0\n",
    "        \n",
    "        if root.right and root.val == root.right.val:\n",
    "            right += 1\n",
    "        else:\n",
    "            right = 0\n",
    "        \n",
    "        self.maxLen = max(self.maxLen, left + right)\n",
    "        return max(left, right)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    maxlength = 0\n",
    "    def longestUnivaluePath(self, root: TreeNode) -> int:\n",
    "        self.searchlength(root)\n",
    "        return self.maxlength\n",
    "\n",
    "    def searchlength(self, root):\n",
    "        if root == None:\n",
    "            return 0\n",
    "        leftlen = self.searchlength(root.left)\n",
    "        if root.left == None or root.left.val != root.val:\n",
    "            leftlen = 0\n",
    "        rightlen = self.searchlength(root.right)\n",
    "        if root.right == None or root.right.val != root.val:\n",
    "            rightlen = 0\n",
    "\n",
    "        len = max(leftlen, rightlen)\n",
    "        self.maxlength = max(self.maxlength, leftlen + rightlen)\n",
    "        return len + 1\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestUnivaluePath(self, root):\n",
    "        self.res = 0\n",
    "        self.dfs(root)\n",
    "        return self.res\n",
    "\n",
    "    def dfs(self, node):\n",
    "        if not node:\n",
    "            return node\n",
    "        left = self.dfs(node.left)\n",
    "        right = self.dfs(node.right)\n",
    "        left_arrow = right_arrow = 0    #初始化为0， 如果值不等，就为0.\n",
    "        if node.left and node.left.val == node.val:\n",
    "            left_arrow = left + 1\n",
    "        if node.right and node.right.val == node.val:\n",
    "            right_arrow = right + 1\n",
    "        self.res = max(self.res, left_arrow + right_arrow)  #找出最大值\n",
    "        return max(left_arrow, right_arrow)                 #返回左右最大值\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def longestUnivaluePath(self, root: TreeNode) -> int:\n",
    "        if (not root):\n",
    "            return 0\n",
    "        answer = 0\n",
    "        array = [root]\n",
    "        i = 0\n",
    "        while (i < len(array)):\n",
    "            if (array[i].left):\n",
    "                array.append(array[i].left)\n",
    "            if (array[i].right):\n",
    "                array.append(array[i].right)\n",
    "            i += 1\n",
    "        for j in range(len(array)):\n",
    "            if (array[-j-1].left):\n",
    "                if (array[-j-1].val == array[-j-1].left.val):\n",
    "                    array[-j-1].left = max(array[-j-1].left.left, array[-j-1].left.right) + 1\n",
    "                else :\n",
    "                    array[-j-1].left = 0\n",
    "            else :\n",
    "                array[-j-1].left = 0\n",
    "            if (array[-j-1].right):\n",
    "                if (array[-j-1].val == array[-j-1].right.val):\n",
    "                    array[-j-1].right = max(array[-j-1].right.left, array[-j-1].right.right) + 1\n",
    "                else :\n",
    "                    array[-j-1].right = 0\n",
    "            else :\n",
    "                array[-j-1].right = 0\n",
    "            answer = max(answer, array[-j-1].left + array[-j-1].right)\n",
    "        return answer"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def longestUnivaluePath(self, root: Optional[TreeNode]) -> int:\n",
    "        ### left 存储以当前节点为根节点的最长路径\n",
    "        ### right 存储该节点极其子节点的最长路径\n",
    "        if not root:\n",
    "            return 0\n",
    "        if root.left:\n",
    "            self.longestUnivaluePath(root.left)\n",
    "        if root.right:\n",
    "            self.longestUnivaluePath(root.right)\n",
    "        res = 0\n",
    "        max_val = 0\n",
    "        left_max = 0\n",
    "        if root.left and root.right and root.left.val == root.val and root.right.val == root.val:\n",
    "            max_val = root.left.left + root.right.left + 2\n",
    "            left_max = max(root.left.left, root.right.left) + 1\n",
    "        elif root.left and root.left.val == root.val:\n",
    "            left_max = root.left.left + 1\n",
    "            max_val = root.left.right\n",
    "        elif root.right and root.right.val == root.val:\n",
    "            left_max = root.right.left+1\n",
    "            max_val = root.right.right\n",
    "        if root.left:\n",
    "            max_val = max(max_val, root.left.right)\n",
    "        if root.right:\n",
    "            max_val = max(max_val, root.right.right)\n",
    "        root.left = left_max\n",
    "        root.right = max(max_val, left_max)\n",
    "        # print(root.val, root.left, root.right)\n",
    "        return root.right"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def longestUnivaluePath(self, root: Optional[TreeNode]) -> int:\n",
    "        if not root:\n",
    "            return 0\n",
    "        if root.left:\n",
    "            self.longestUnivaluePath(root.left)\n",
    "        if root.right:\n",
    "            self.longestUnivaluePath(root.right)\n",
    "        res = 0\n",
    "        max_val = 0\n",
    "        left_max = 0\n",
    "        if root.left and root.right and root.left.val == root.val and root.right.val == root.val:\n",
    "            max_val = root.left.left + root.right.left + 2\n",
    "            left_max = max(root.left.left, root.right.left) + 1\n",
    "        elif root.left and root.left.val == root.val:\n",
    "            left_max = root.left.left + 1\n",
    "            max_val = root.left.right\n",
    "        elif root.right and root.right.val == root.val:\n",
    "            left_max = root.right.left+1\n",
    "            max_val = root.right.right\n",
    "        if root.left:\n",
    "            max_val = max(max_val, root.left.right)\n",
    "        if root.right:\n",
    "            max_val = max(max_val, root.right.right)\n",
    "        root.left = left_max\n",
    "        root.right = max(max_val, left_max)\n",
    "        # print(root.val, root.left, root.right)\n",
    "        return root.right"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.root_list = []\n",
    "        self.max_path_list = [0]\n",
    "    def longestUnivaluePath(self, root: Optional[TreeNode]) -> int:\n",
    "        self.root_list.append(root)\n",
    "        self.find_same_root(root)\n",
    "\n",
    "        for r in self.root_list:\n",
    "            self.count_tree_node(r)\n",
    "        \n",
    "        return max(self.max_path_list)\n",
    "\n",
    "    def find_same_root(self, phead):\n",
    "        if phead is None or (phead.left is None and phead.right is None):\n",
    "            return\n",
    "\n",
    "        if phead.left and phead.left.val == phead.val:\n",
    "            self.find_same_root(phead.left)\n",
    "        elif phead.left and phead.left.val != phead.val:\n",
    "            self.root_list.append(phead.left)\n",
    "            self.find_same_root(phead.left)\n",
    "            phead.left = None\n",
    "\n",
    "        if phead.right and phead.right.val == phead.val:\n",
    "            self.find_same_root(phead.right)\n",
    "        elif phead.right and phead.right.val != phead.val:\n",
    "            self.root_list.append(phead.right)\n",
    "            self.find_same_root(phead.right)\n",
    "            phead.right = None\n",
    "\n",
    "        \n",
    "\n",
    "    def count_tree_node(self, phead):\n",
    "\n",
    "        if phead is None:\n",
    "            return 0\n",
    "\n",
    "        left_node_cnt = self.count_tree_node(phead.left)\n",
    "        right_node_cnt = self.count_tree_node(phead.right)\n",
    "        self.max_path_list.append(left_node_cnt + right_node_cnt)\n",
    "\n",
    "        return max(left_node_cnt, right_node_cnt) + 1\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def longestUnivaluePath(self, root: TreeNode) -> int:\n",
    "        res = [0]\n",
    "        self.helper(root, res)\n",
    "\n",
    "        return res[0]\n",
    "    \n",
    "    \"\"\"\n",
    "    递归出口：当前root的左右子树的最长同值路径\n",
    "    递归返回值：当前root的最长同值路径\n",
    "    \"\"\"\n",
    "    def helper(self, root, res):\n",
    "        # base case\n",
    "        if not root:\n",
    "            return 0\n",
    "\n",
    "        # 获得左右子树的最长同值路径\n",
    "        leftLgst = self.helper(root.left, res)\n",
    "        rightLgst = self.helper(root.right, res)\n",
    "\n",
    "        # 当前root的最长同值路径为：\n",
    "        # 情况1： left 和 root 的值一样，最长同值路径 = 左子树路径 + 1\n",
    "        # 情况2： right 和 root 的值一样，最长同值路径 = 左子树路径 + 1\n",
    "        # 情况3： 左右子树值和root都不一样，最长同值路径 = 0\n",
    "        # 以上三种情况选最大值\n",
    "        lr = 0\n",
    "        rr = 0\n",
    "        longest = None\n",
    "        if root.left and root.val == root.left.val:\n",
    "            lr = leftLgst + 1\n",
    "        if root.right and root.val == root.right.val:\n",
    "            rr = rightLgst + 1\n",
    "        longest = max(lr, rr)\n",
    "\n",
    "        # 经过当前root的数的最长同值路径\n",
    "        curLgst = 0\n",
    "        if root.left and root.right and root.left.val == root.right.val and root.val == root.left.val:\n",
    "            curLgst = lr + rr\n",
    "\n",
    "        # 更新全局最长同值路径\n",
    "        res[0] = max(res[0], lr, rr, curLgst)\n",
    "         \n",
    "        # 返回当前root最长同值路径\n",
    "        return longest"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def longestUnivaluePath(self, root: TreeNode) -> int:\n",
    "        self.res = 0\n",
    "        def dfs(node):\n",
    "            L = R = 0\n",
    "            if not node:\n",
    "                return 0\n",
    "            left = dfs(node.left)\n",
    "            right = dfs(node.right)\n",
    "            if node.left:\n",
    "                if node.val == node.left.val:\n",
    "                    L = left +1\n",
    "            if node.right:\n",
    "                if node.val == node.right.val:\n",
    "                    R = right +1\n",
    "            self.res = max(self.res,L+R)\n",
    "            return max(L,R)\n",
    "        dfs(root)\n",
    "        return self.res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.max = 0\n",
    "    \n",
    "    def longestUnivaluePath(self, root):\n",
    "        if root is None:\n",
    "            return 0\n",
    "        self.dfs(root, root.val)\n",
    "        return self.max\n",
    "    \n",
    "    def dfs(self, root, value):\n",
    "        if root is None:\n",
    "            return 0\n",
    "        left = self.dfs(root.left, root.val)\n",
    "        right = self.dfs(root.right, root.val)\n",
    "        self.max = max(self.max, left + right)\n",
    "        \n",
    "        if value != root.val:\n",
    "            return 0\n",
    "        else:\n",
    "            return 1 + max(left, right)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode(object):\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    " \n",
    "class Solution(object):\n",
    "    maxLen = 0\n",
    "    def longestUnivaluePath(self, root):\n",
    "        \"\"\"\n",
    "        :type root: TreeNode\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        if not root:\n",
    "            return 0\n",
    "        self.getMaxLen(root, root.val)\n",
    "        return self.maxLen\n",
    "    \n",
    "    def getMaxLen(self, root, val):\n",
    "        if not root:\n",
    "            return 0\n",
    "        left = self.getMaxLen(root.left, root.val)\n",
    "        right = self.getMaxLen(root.right, root.val)\n",
    "        self.maxLen = max(self.maxLen, left + right)\n",
    "        if root.val == val:\n",
    "            return max(left, right) + 1\n",
    "        return 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def longestUnivaluePath(self, root: Optional[TreeNode]) -> int:\n",
    "        ans = 0\n",
    "        def dfs(node: Optional[TreeNode]) -> int:\n",
    "            if node is None:\n",
    "                return 0\n",
    "            left = dfs(node.left)\n",
    "            right = dfs(node.right)\n",
    "            left1 = left + 1 if node.left and node.left.val == node.val else 0\n",
    "            right1 = right + 1 if node.right and node.right.val == node.val else 0\n",
    "            nonlocal ans\n",
    "            ans = max(ans, left1 + right1)\n",
    "            return max(left1, right1)\n",
    "        dfs(root)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def longestUnivaluePath(self, root):\n",
    "        maxNum = 0\n",
    "        def dfs(root):\n",
    "            if not root: return 0\n",
    "            left = dfs(root.left)\n",
    "            right = dfs(root.right)\n",
    "            if root.left and root.left.val == root.val:\n",
    "                left += 1\n",
    "            else:\n",
    "                left = 0\n",
    "            if root.right and root.right.val == root.val:\n",
    "                right += 1\n",
    "            else:\n",
    "                right = 0\n",
    "            \n",
    "            nonlocal maxNum\n",
    "            maxNum = max(maxNum, left + right)\n",
    "\n",
    "            return max(left, right)\n",
    "                \n",
    "        dfs(root)\n",
    "        return maxNum"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def longestUnivaluePath(self, root: Optional[TreeNode]) -> int:\n",
    "        result = 0\n",
    "        def dfs(node):\n",
    "            nonlocal result\n",
    "            if not node:\n",
    "                return 0\n",
    "            left = dfs(node.left)\n",
    "            right = dfs(node.right)\n",
    "\n",
    "            left_temp = left + 1 if node.left and node.val == node.left.val else 0\n",
    "            right_temp = right + 1 if node.right and node.val == node.right.val else 0\n",
    "            result = max(result, left_temp + right_temp)\n",
    "            return max(left_temp, right_temp)\n",
    "        \n",
    "        dfs(root)\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def longestUnivaluePath(self, root: Optional[TreeNode]) -> int:\n",
    "        res = 0\n",
    "        def dfs(node):\n",
    "            nonlocal res\n",
    "            v = node.val\n",
    "            r = 0\n",
    "            r1 = 0\n",
    "            r2 = 0\n",
    "            l = 0\n",
    "            ri = 0\n",
    "            if node.left:\n",
    "                l = dfs(node.left)\n",
    "                if node.left.val==v:\n",
    "                    r1 += l + 1\n",
    "            if node.right:\n",
    "                ri = dfs(node.right)\n",
    "                if node.right.val==v:\n",
    "                    r2 += ri + 1\n",
    "            res = max(res, r1+r2)\n",
    "            return max(r1, r2)\n",
    "        if not root:\n",
    "            return 0\n",
    "        dfs(root)\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    # def __init__(self,):\n",
    "    #     self.res=0\n",
    "\n",
    "    # 类全局变量，可通过self.res来修改值，不需要使用global关键字，如果不在类里，而这个变量又声明在函数外，则可以使用global关键字\n",
    "    res=0\n",
    "\n",
    "    def dfs(self,root):\n",
    "        if root==None:\n",
    "            return 0\n",
    "        \n",
    "        left=self.dfs(root.left)\n",
    "        right=self.dfs(root.right)\n",
    "        left=left+1 if root.left and root.val==root.left.val else 0            \n",
    "        right=right+1 if root.right and root.val==root.right.val else 0\n",
    "        self.res=max(self.res,left+right)\n",
    "        return max(left,right)\n",
    "       \n",
    "    def longestUnivaluePath(self, root: Optional[TreeNode]) -> int:\n",
    "        if root==None:\n",
    "            return 0\n",
    "        self.dfs(root)\n",
    "        return self.res\n",
    "\n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def longestUnivaluePath(self, root: Optional[TreeNode]) -> int:\n",
    "        def dfs(node):\n",
    "            nonlocal ans\n",
    "            if not node:\n",
    "                return 0\n",
    "            left = dfs(node.left)\n",
    "            right = dfs(node.right)\n",
    "            left1 = left + 1 if node.left and node.left.val == node.val else 0\n",
    "            right1 = right + 1 if node.right and node.right.val == node.val else 0\n",
    "            ans = max(ans, left1 + right1)\n",
    "            return max(left1, right1)\n",
    "        \n",
    "        ans = 0\n",
    "        dfs(root)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.result = 0\n",
    "    def longestUnivaluePath(self, root: Optional[TreeNode]) -> int:\n",
    "        if root==None:\n",
    "            return 0\n",
    "        self.dfs(root)\n",
    "        return self.result\n",
    "        \n",
    "    def dfs(self,root):\n",
    "        if root==None:\n",
    "            return 0\n",
    "        left = 0\n",
    "        right = 0\n",
    "        left_1 = self.dfs(root.left)\n",
    "        right_1 = self.dfs(root.right)\n",
    "        if root.left and root.left.val == root.val:\n",
    "            left = left_1+1\n",
    "        if root.right and root.right.val == root.val:\n",
    "            right = right_1+1\n",
    "        self.result = max(self.result,left+right)\n",
    "        return max(left,right)\n",
    "            \n",
    "\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    # def __init__(self,):\n",
    "    #     self.res=0\n",
    "\n",
    "    # 类全局变量，可通过self.res来修改值，不需要使用global关键字，如果不在类里，而这个变量又声明在函数外，则可以使用global关键字\n",
    "    # 和使用def __init__(self,)来声明不同的是使用初始化方法声明，则在每个函数里都会拥有自己的res属性，值可以不同，但使用类全局变量则在类中的不同函数里，他们的值是相同的，即在一个函数里更新，则另一个函数里的res属性值也会更改\n",
    "    res=0\n",
    "\n",
    "    def dfs(self,root):\n",
    "        if root==None:\n",
    "            return 0\n",
    "        \n",
    "        left=self.dfs(root.left)\n",
    "        right=self.dfs(root.right)\n",
    "        left=left+1 if root.left and root.val==root.left.val else 0            \n",
    "        right=right+1 if root.right and root.val==root.right.val else 0\n",
    "        self.res=max(self.res,left+right)\n",
    "        return max(left,right)\n",
    "       \n",
    "    def longestUnivaluePath(self, root: Optional[TreeNode]) -> int:\n",
    "        if root==None:\n",
    "            return 0\n",
    "        self.dfs(root)\n",
    "        return self.res\n",
    "\n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    # def __init__(self,):\n",
    "    #     self.res=0\n",
    "\n",
    "    # 类全局变量，可通过self.res来修改值，不需要使用global关键字，如果不在类里，而这个变量又声明在函数外，则可以使用global关键字\n",
    "    res=0\n",
    "\n",
    "    def dfs(self,root):\n",
    "        if root==None:\n",
    "            return 0\n",
    "        \n",
    "        left=self.dfs(root.left)\n",
    "        right=self.dfs(root.right)\n",
    "        left=left+1 if root.left and root.val==root.left.val else 0            \n",
    "        right=right+1 if root.right and root.val==root.right.val else 0\n",
    "        self.res=max(self.res,left+right)\n",
    "        return max(left,right)\n",
    "       \n",
    "    def longestUnivaluePath(self, root: Optional[TreeNode]) -> int:\n",
    "        if root==None:\n",
    "            return 0\n",
    "        self.dfs(root)\n",
    "        return self.res\n",
    "\n",
    "        \n",
    "\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
